package one;

import org.junit.jupiter.api.Test;

import java.util.*;

public class One {

    // 2. 两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int node1 = l1 != null ? l1.val : 0;
            int node2 = l2 != null ? l2.val : 0;
            int val = node1 + node2 + carry;
//            保存进位
            carry = val / 10;
            if (head == null) {
                head = new ListNode(val % 10);
                tail = head;
            } else {
                tail.next = new ListNode(val % 10);
                tail = tail.next;
            }
            if (l1 != null)
                l1 = l1.next;
            if (l2 != null)
                l2 = l2.next;
            // 需要把进位的数数字放进去，如果不是下次会覆盖这个数
            if (carry > 0)
                tail.next = new ListNode(carry);
        }
        return head;
    }

    @Test
    public void test() {
        int abcabcbb = lengthOfLongestSubstring("pwwkew");
    }

    // 3. 无重复字符的最长子串 滑动窗口
    public int lengthOfLongestSubstring(String s) {
        if (s == null || "".equals(s)) return 0;
        HashSet<Character> hashSet = new HashSet<>();
        int start = 0, end = 0, result = 0;
        while (end < s.length()) {
            // 添加不成功说明里面有重复的字符 需要计算出来现有的长度，
            // 然后移除开始位置所有重复的字符 直至添加成功
            if (!hashSet.add(s.charAt(end))) {
                result = Math.max(result, hashSet.size());
                while (!hashSet.add(s.charAt(end))) {
                    hashSet.remove(s.charAt(start));
                    start++;
                }
            }
            end++;
        }
        return Math.max(result, hashSet.size());
    }

    //5. 最长回文子串 从中间往两边扩展
    public String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        String result = "";
        for (int i = 0; i < chars.length; i++) {

            int resultStart = i - 1, resultEnd = i + 1;
            result = expandAroundCenter(s, chars, result, i, resultStart, resultEnd);
            resultStart = i;
            resultEnd = i + 1;
            result = expandAroundCenter(s, chars, result, i, resultStart, resultEnd);
        }

        return result;
    }

    private String expandAroundCenter(String s, char[] chars, String result, int i, int resultStart, int resultEnd) {
        while (resultStart >= 0 && resultEnd < chars.length && chars[resultStart] == chars[resultEnd]) {
            resultStart--;
            resultEnd++;
        }
        if (result.length() < resultEnd - resultStart) result = s.substring(resultStart + 1, resultEnd);
        return result;
    }

    //7. 整数反转
    public int reverse(int x) {
        int result = 0;
        while (x != 0) {
            if (result > Integer.MAX_VALUE / 10 || result < Integer.MIN_VALUE / 10) {
                return 0;
            }
            result = result * 10 + x % 10;
            x /= 10;
        }
        return result;
    }

    // 9.判断回文数字
    @Test
    public boolean isPalindrome(int x) {
        String s = String.valueOf(x);
        int start = 0, end = s.length() - 1;
        while (true) {
            // 指针相遇或者指针错位的时候返回true
            if (start == end || end + 1 == start) return true;
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            } else {
                start++;
                end--;
            }
        }
    }


    HashMap<Integer, String> dir = new HashMap<>() {{
        put(1000, "M");
        put(900, "CM");
        put(500, "D");
        put(400, "CD");
        put(100, "C");
        put(90, "XC");
        put(50, "L");
        put(40, "XL");
        put(10, "X");
        put(9, "IX");
        put(5, "V");
        put(4, "IV");
        put(1, "I");
    }};

    // 12. 整数转罗马数字
    public String intToRoman(int num) {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < num / 1000; i++) {
            result.append(dir.get(1000));
        }
        num %= 1000;
        for (int i = 0; i < num / 900; i++) {
            result.append(dir.get(900));
        }
        num %= 900;
        for (int i = 0; i < num / 500; i++) {
            result.append(dir.get(500));
        }
        num %= 500;
        for (int i = 0; i < num / 400; i++) {
            result.append(dir.get(400));
        }
        num %= 400;
        for (int i = 0; i < num / 100; i++) {
            result.append(dir.get(100));
        }
        num %= 100;
        for (int i = 0; i < num / 90; i++) {
            result.append(dir.get(90));
        }
        num %= 90;
        for (int i = 0; i < num / 50; i++) {
            result.append(dir.get(50));
        }
        num %= 50;
        for (int i = 0; i < num / 40; i++) {
            result.append(dir.get(40));
        }
        num %= 40;
        for (int i = 0; i < num / 10; i++) {
            result.append(dir.get(10));
        }
        num %= 10;
        for (int i = 0; i < num / 9; i++) {
            result.append(dir.get(9));
        }
        num %= 9;
        for (int i = 0; i < num / 5; i++) {
            result.append(dir.get(5));
        }
        num %= 5;
        for (int i = 0; i < num / 4; i++) {
            result.append(dir.get(4));
        }
        num %= 4;
        for (int i = 0; i < num; i++) {
            result.append(dir.get(1));
        }
        return result.toString();
    }

    // 17. 电话号码的字母组合 回溯算法做
    HashMap<Character, String> numMap = new HashMap<>() {{
        this.put('2', "abc");
        this.put('3', "def");
        this.put('4', "ghi");
        this.put('5', "jkl");
        this.put('6', "mno");
        this.put('7', "qprs");
        this.put('8', "tuv");
        this.put('9', "wxyz");
    }};

    public List<String> letterCombinations(String digits) {
        ArrayList<String> resultList = new ArrayList<>();
        letterCombinations(digits, 0, new StringBuilder(), resultList);
        return resultList;

    }

    public void letterCombinations(String digits, int start, StringBuilder result,
                                   ArrayList<String> resultList) {
        if (digits.length() == start) return;
        String s = numMap.get(digits.charAt(start));
        for (int i = 0; i < s.length(); i++) {
            result.append(s.charAt(i));
            letterCombinations(digits, start + 1, result, resultList);
            if (result.length() == digits.length())
                resultList.add(result.toString());
            result.deleteCharAt(start);
        }
    }

    // 19. 删除链表的倒数第 N 个结点 采用栈的方式实现，
    public ListNode removeNthFromEnd(ListNode head, int n) {
        head = new ListNode(1, new ListNode(2, new ListNode(3, null)));
        ListNode listNode = new ListNode(0, head);
        LinkedList<ListNode> stack = new LinkedList<>();
        ListNode temp = listNode;
        while (temp != null) {
            stack.addFirst(temp);
            temp = temp.next;
        }
        for (int i = 0; i < n; i++) {
            stack.removeFirst();
        }
        ListNode peek = stack.getFirst();
        peek.next = peek.next.next;
        return listNode.next;
    }

    // 22. 括号生成
    public List<String> generateParenthesis(int n) {
        ArrayList<String> result = new ArrayList<>();
        generateParenthesis(n, 0, 0, result, "");
        return result;
    }

    // ((( -> ((()))  -> (()(
    public void generateParenthesis(int n, int leftLength, int rightLength, List<String> result, String path) {
        // 如果左括号和右括号的数量都等于 n 添加该结果
        if (leftLength == n && rightLength == n) result.add(path);
        else {
            // 注意不能用++ 因为++ 会永久改变值，所以只能用+1的方式来传递参数
            // 递归到最深处，然后倒退回来
            if (n > leftLength) {
                generateParenthesis(n, leftLength + 1, rightLength, result, path + "(");
            }

            if (n > rightLength && leftLength > rightLength) {
                generateParenthesis(n, leftLength, rightLength + 1, result, path + ")");
            }
        }
    }

    //39. 组合总和
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, target, path, result);
        return result;
    }

    /**
     * @param candidates 原数组
     * @param begin      搜索数组下标的起点
     * @param target     还剩下数
     * @param path       已找到的路径
     * @param res        结果集合
     */
    private void dfs(int[] candidates, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {
        // 目标小于0之后没有子节点，直接返回
        if (target > 0) {
            for (int i = begin; i < candidates.length; i++) {
                // 可能是结果，先添加进去
                path.addLast(candidates[i]);
                dfs(candidates, i, target - candidates[i], path, res);
                // 删除结果集
                path.removeLast();
            }
        } else if (target == 0) {
            // target == 0 找到了对应的路径，添加到结果集当中
            res.add(new ArrayList<>(path));
        }
    }

    //46. 全排列
    public List<List<Integer>> permute(int[] nums) {
        ArrayList<List<Integer>> result = new ArrayList<>();
        permuteDFS(nums, new ArrayDeque<>(), result, new HashMap<>());
        return result;
    }

    // 55. 跳跃游戏 贪心算法
    public boolean canJump(int[] nums) {
        // 最远可以到达的位置
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > max) return false;
            max = Math.max(max, i + nums[i]);
            if (max >= nums.length-1) return true;
        }
        return false;
    }

    public void permuteDFS(int[] nums,
                           ArrayDeque<Integer> arrayDeque,
                           List<List<Integer>> result,
                           Map<Integer, Boolean> used) {
        if (arrayDeque.size() == nums.length) return;
        for (int i = 0; i < nums.length; i++) {
            // 如果使用过当前的数字，开始下次循环
            if (used.get(i) != null && used.get(i)) {
                continue;
            }
            // 记录下当前值nums[i]被使用下次不再使用
            used.put(i, true);
            arrayDeque.addLast(nums[i]);
            permuteDFS(nums, arrayDeque, result, used);
            if (arrayDeque.size() == nums.length)
                result.add(arrayDeque.stream().toList());
            // 移除值nums[i]的使用
            used.remove(i);
            arrayDeque.removeLast();
        }
    }

    //    70. 爬楼梯
    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int result = 0, f0 = 1, f1 = 2;
        for (int i = 3; i <= n; i++) {
            result = f0 + f1;
            f0 = f1;
            f1 = result;
        }
        return result;
    }

    //75. 颜色分类
    public void sortColors(int[] nums) {
        int start = 0, end = nums.length - 1;
        for (int i = 0; i < nums.length; i++) {
            if (start == end) return;
            // 如果开始的值== 0 则下移动指针，
            if (nums[start] == 0) {
                start++;
                continue;
            }
            if (nums[end] == 2) {
                end--;
                continue;
            }
            // 到这里开始指针不为0，结束指针不为2
            if (nums[start] == 2) {
                nums[start] = nums[end];
                nums[end] = 2;
                end--;
                continue;
            }
            if (nums[end] == 0) {
                nums[end] = nums[start];
                nums[start] = 0;
                start++;
                continue;
            }
            // 可能还存在一种可能，就是 101，所以需要循环一边看看有没有这种情况
            for (int i1 = 0; i1 < end - start + 1; i1++) {
                if (nums[i1 + start] == 0) {
                    nums[i1 + start] = nums[start];
                    nums[start] = 0;
                    start++;
                } else if (nums[i1 + start] == 2) {
                    nums[i1 + start] = nums[end];
                    nums[end] = 2;
                    end--;
                }
            }
        }
    }

    //  88. 合并两个有序数组 双指针做法，从后往前排序
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        while (n > 0) {
            if (m > 0 && nums1[m - 1] > nums2[n - 1]) {
                nums1[m + n - 1] = nums1[m - 1];
                m--;
            } else {
                nums1[m + n - 1] = nums2[n - 1];
                n--;
            }
        }
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}